package demo.practice.uf;

public class UFRankUnionCompressPath {


    int[] parent;
    int[] rank;//树的层数
    int plant;  //一共有多少株树

    public UFRankUnionCompressPath(int size) {
        plant = size;
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int findP(int x) {//查询操作，其实是查询  根节点
        if (x < 0 || x >= parent.length)
            return -1;  //或者直接抛出异常

        while (parent[x] != parent[parent[x]])
        //如果parent[x]==parent[parent[x]] 说明这颗树到了第二层，或者第一层
        //第一层 因为parent[x]=x所以有  parent[x]==parent[parent[x]]
        //第二层 因为第二层的parent是根节点 有： parent[x]= root  所以有 parent[parent[x]]= parent[root]  而本身 parent[root]=root
        {
            // x = parent[x];  //
            parent[x] = parent[parent[x]]; //将下层节点往顶层提升，最终
        }
        return parent[x];
    }


    public void join(int a, int b) {
        int ap = findP(a);
        int bp = findP(b);
        if (ap != bp) {
            plant--;
            //a的层数越高，就将层数少的合并到层数高的上面
            if (rank[ap] > rank[bp])
                parent[bp] = ap;
            else if (rank[ap] < rank[bp]) {
                parent[ap] = bp;
            } else {
                //相同情况的话，随便就可以
                parent[ap] = bp;
                rank[bp]++;
            }
        }
    }

    public int getPlant() {
        return plant;
    }

    public boolean isJoined(int a, int b) { //两个节点是否是  连接的
        return findP(a) == findP(b);
    }
}
